package newcoder_exp.meituan;

import tree.*;
import java.util.*;

import org.junit.Test;

public class Meituan11 {
    
    //1. 二叉树最大宽度【力扣622】
    //错误，没有考虑到右边全部为空的情况`_`
    class Solution {
        //宽度优先遍历
        public int widthOfBinaryTree(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            if (root == null) return 0;
            queue.offer(root);
            int res = 1;
            while (!queue.isEmpty()) {
                int n = queue.size(), count = 0;
                for (int i = 0; i < n; i++) {
                    TreeNode cur = queue.poll();
                    if (cur.left != null) {
                        count++;
                        queue.offer(cur.left);
                    } else if (count > 0) { //左边已经出现了非空节点，因此计时其实已经开始
                        count++;
                    }
                    if (cur.right != null) {
                        count++;
                        queue.offer(cur.left);
                    } else if (count > 0) {
                        count++;
                    }
                }
                res = Math.max(count, res);
            }
            return res;
        }
    }

    class Solution2 {
        //思路二：使用双端队列存储Node类，Node类包含树节点自身，还包含了树节点所在下标，下标通过父节点找到
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            Deque<Node> deque = new LinkedList<>();
            deque.offer(new Node(root, 0));
            Node cur, left, right;
            int res = 1;
            while (!deque.isEmpty()) {
                //!!!第一版错误：应该将判断最大宽度放到遍历外边，因为中途会添加下一层的节点，就会导致拿下层结点算差距
                int n = deque.size();
                left = deque.peekFirst();
                right = deque.peekLast();
                res = Math.max(res, (right.idx - left.idx + 1));
                for (int i = 0; i < n; i++) {
                cur = deque.pollFirst();
                    if (cur.tn.left != null) {
                        deque.offerLast(new Node(cur.tn.left, 2 * cur.idx + 1));
                    }
                    if (cur.tn.right != null) {
                        deque.offerLast(new Node(cur.tn.right, 2 * cur.idx + 2));
                    }
                }
            }
            return res;
        }

        class Node {
            TreeNode tn;
            int idx;
            public Node(TreeNode tn, int idx) {
                this.tn = tn;
                this.idx = idx;
            }
        }
    }

    @Test
    public void test() {
        TreeNode root = TreeUtils.createTree(new Integer[]{1,2,3,4,5});
        Solution2 s = new Solution2();
        int res = s.widthOfBinaryTree(root);
        System.out.println(res);
    }


    class Solution3 {
        //方案3：使用Map记录当前层的最左节点的位置，每遍历到一个节点，去试图从Map中获取这个节点的最左节点，使用当前位置-最左+1求得间距，并试图去更新最大值
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            res = 1;
            dfs(root, 0, 0);
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>(); //KEY:层数，Value：最左节点下标
        int res;

        //前序遍历可以保证到达每一层是先遍历最左的节点。
        public void dfs(TreeNode root, int level, int idx) {
            if (root == null) return;
            int left = -1;
            if (map.containsKey(level)) {
                left = map.get(level);
                res = Math.max(idx - left + 1, res);
            } else map.put(level, idx); //若不存在最左节点，爷就是最左节点

            dfs(root.left, level + 1, idx * 2 + 1);
            dfs(root.right, level + 1, idx * 2 + 2);
        }
    }


    // 2. . 算法题 ：实现缓存 put和get方法 size1000 大于1000的时候用LRU 算法 淘汰20%
    class LRUCache {
        int capacity;
        int size;
        DList dlist;
        Map<Integer, DNode> map;

        public LRUCache(int capacity) {
            this.map = new HashMap<>();
            this.dlist = new DList(capacity);
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if (map.containsKey(key)) {
                DNode res = map.get(key);
                this.dlist.moveToFirst(res);
                return res.value;
            }
            else return -1;
        }
        
        public void put(int key, int value) {
            if (map.containsKey(key)) {
                DNode node = map.get(key);
                node.value = value;
                dlist.moveToFirst(node);
                return;
            }
            dlist.insert(key, value);
            map.put(key, dlist.head);
            while (dlist.size > capacity) {
                map.remove(dlist.tail.key);
                dlist.deleteLast();
            }
        }


        class DList {
            DNode head, tail;
            int size, capacity;

            public DList(int capacity) {
                this.size = 0;
                this.capacity = capacity;
            }

            public void insert(int key, int value) {
                DNode node = new DNode(key, value);
                if (this.head == null) {
                    this.head = node;
                    this.tail = head;
                } else {
                    node.next = head;
                    head.prev = node;
                    this.head = node;
                }
                this.size++;
            }

            public void deleteLast() {
                if (tail == head) {
                    tail = head = null;
                    return;
                }
                tail = tail.prev;
                tail.next = null;
                this.size--;
            }

            public void moveToFirst(DNode cur) {
                if (cur.prev == null) return;
                if (cur == this.tail) {
                    this.tail = cur.prev;
                    tail.next = null;
                }
                if (cur.next != null) {
                    cur.next.prev = cur.prev;
                }
                cur.prev.next = cur.next;
                cur.next = head;
                cur.prev = null;
                head.prev = cur;
                this.head = cur;
            }
        }

        class DNode {
            int key;
            int value;
            DNode prev, next;
            
            public DNode(int key, int value) {
                this.key = key;
                this.value = value;
            }

            @Override
            public String toString() {
                return this.key + "";
            }
        }
    }

    class LRUCacheBig {
        int capacity;
        int size;
        DList dlist;
        Map<Integer, DNode> map;

        public LRUCacheBig(int capacity) {
            this.map = new HashMap<>();
            this.dlist = new DList(capacity);
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if (map.containsKey(key)) {
                DNode res = map.get(key);
                this.dlist.moveToFirst(res);
                return res.value;
            }
            else return -1;
        }
        
        public void put(int key, int value) {
            dlist.insert(key, value);
            map.put(key, dlist.head);
            if (dlist.size > capacity) {
                map.remove(dlist.tail.key);
                dlist.deleteLast();
            }
        }


        class DList {
            DNode head, tail;
            int size, capacity;

            public DList(int capacity) {
                this.size = 0;
                this.capacity = capacity;
            }

            public void insert(int key, int value) {
                DNode node = new DNode(key, value);
                if (this.head == null) {
                    this.head = node;
                    this.tail = head;
                } else {
                    node.next = head;
                    head.prev = node;
                    this.head = node;
                }
                this.size++;
            }

            public void deleteLast() {
                tail = tail.prev;
                tail.next = null;
                this.size--;
            }

            public void moveToFirst(DNode cur) {
                if (cur.prev == null) return;
                if (cur == this.tail) this.tail = cur.prev;
                if (cur.next != null) {
                    cur.next.prev = cur.prev;
                }
                cur.prev.next = cur.next;
                cur.next = head;
                head.prev = cur;
                this.head = cur;
            }
        }

        class DNode {
            int key;
            int value;
            DNode prev, next;
            
            public DNode(int key, int value) {
                this.key = key;
                this.value = value;
            }

            @Override
            public String toString() {
                return this.key + "";
            }
        }
    }

    @Test
    public void test2() {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        int res1 = cache.get(1);
        cache.put(3, 3);
        int res2 = cache.get(2);
        cache.put(4,4);
        int res3 = cache.get(1);
        int res4 = cache.get(3);
        int res5 = cache.get(4);

        System.out.println(res1);
        System.out.println(res2);
        System.out.println(res3);
        System.out.println(res4);
        System.out.println(res5);

    }

    //["LRUCache","put","put","put","put","get","get"][[2],[2,1],[1,1],[2,3],[4,1],[1],[2]]
}


/* 
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
["LRUCache","put","put","put","put","get","get"]
[[2],[2,1],[1,1],[2,3],[4,1],[1],[2]]
["LRUCache","put","put","put","put","get","get","get","get","put","get","get","get","get","get"]
[[3],[1,1],[2,2],[3,3],[4,4],[4],[3],[2],[1],[5,5],[1],[2],[3],[4],[5]]
["LRUCache","put","put","get","put","put","get"]
[[2],[2,1],[2,2],[2],[1,1],[4,1],[2]]

["LRUCache","put","put","put","put","put","get","put","get","get","put","get","put","put","put",
"get","put","get","get","get","get","put","put","get","get","get","put","put","get","put","get","put",
"get","get","get","put","put","put","get","put","get","get","put","put","get","put","put","put","put",
"get","put","put","get","put","put","get","put","put","put","put","put","get","put","put","get","put",
"get","get","get","put","get","get","put","put","put","put","get","put","put","put","put","get","get","get","put","put","put","get","put","put","put","get","put","put","put","get","get","get","put","put","put","put","get","put","put","put","put","put","put","put"]
[[10],[10,13],[3,17],[6,11],[10,5],[9,10],[13],[2,19],[2],[3],[5,25],[8],[9,22],[5,5],[1,30],[11],[9,12],[7],[5],[8],[9],[4,30],[9,3],[9],[10],[10],[6,14],[3,1],[3],[10,11],[8],[2,14],[1],[5],[4],[11,4],[12,24],[5,18],[13],[7,23],[8],[12],[3,27],[2,12],[5],[2,9],[13,4],[8,18],[1,7],[6],[9,29],[8,21],[5],[6,30],[1,12],[10],[4,15],[7,22],[11,26],[8,17],[9,29],[5],[3,4],[11,30],[12],[4,29],[3],[9],[6],[3,4],[1],[10],[3,29],[10,28],[1,20],[11,13],[3],[3,12],[3,8],[10,9],[3,26],[8],[7],[5],[13,17],[2,27],[11,15],[12],[9,19],[2,15],[3,16],[1],[12,17],[9,1],[6,19],[4],[5],[5],[8,1],[11,7],[5,2],[9,28],[1],[2,2],[7,4],[4,22],[7,24],[9,26],[13,28],[11,26]]

*/